package cn.zzf.algs.note.exercise.sort;

import cn.zzf.algs.note.base.collection.v2.LinkedQueue;
import cn.zzf.algs.note.base.sort.Sort;

/**
 * 自底向上的有序队列归并排序。自底向上的有序队列归并排序。
 * 用下面的方法编写一个自底向上的归并排序：给定N个元素，创建N个队列，每个队列包含其中一个元素。
 * 创建一个由这N个队列组成的队列，然后不断用练习2.2.14中的方法将队列的头两个元素归并，并将幸福空间要重新加入到队列结尾，直到队列的队列只剩下一个元素为止。
 * @author GaoFeng2017
 * @date 2020/7/22 10:27
 */
public class Ex_2_2_15_BottomUpQueueMergeSort implements Sort {

    @Override
    public void sort(Comparable[] elements) {

        LinkedQueue<LinkedQueue<Comparable>> elementQueue = new LinkedQueue<>();

        for (Comparable element : elements) {
            elementQueue.enqueue(singletonQueue(element));
        }

        while (elementQueue.size() > 1) {
            LinkedQueue<Comparable> leftElements = elementQueue.dequeue();
            LinkedQueue<Comparable> rightElements = elementQueue.dequeue();

            LinkedQueue<Comparable> mergeResult = Ex_2_2_14_MergeTwoQueue.merge(leftElements, rightElements);
            elementQueue.enqueue(mergeResult);
        }


        LinkedQueue<Comparable> result = elementQueue.dequeue();

        for (int i = 0; i < elements.length; i++) {
            elements[i] = result.dequeue();
        }

    }

    private LinkedQueue<Comparable> singletonQueue(Comparable element) {
        LinkedQueue<Comparable> queue = new LinkedQueue<>();
        queue.enqueue(element);
        return queue;
    }
}
